home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / basic / ubas830.zip / MALM.EXE / RESSOL.UB < prev    next >
Text File  |  1990-08-22  |  719b  |  20 lines
  1.    10   *Ressol(P,A,&R)
  2.    20   ' Algorithm of Shanks to solve x^2 = A (mod P).  The solution
  3.    30   ' is returned in R.  It is assumed that P is an odd prime and
  4.    40   ' that A is a quadratic residue modulo P.
  5.    50   ' 15 May 1990
  6.   100   local S=0,I,J,Limit,N,Z=2,C,B,Te,K
  7.   110   Te=P-1:K=Te\2
  8.   120   repeat inc S:Te=K:K=Te\2 until res
  9.   130   N=modpow(A,Te,P):R=modpow(A,K+1,P)
  10.   140   if N=1 then return endif
  11.   150   while kro(Z,P)<>-1:inc Z wend
  12.   160   C=modpow(Z,Te,P)
  13.   165   repeat Limit=S:B=N
  14.   170   for I=1 to Limit
  15.   180   if B=1 then B=C:S=I-1 else B=(B*B)@P endif
  16.   185   next I
  17.   190   C=(B*B)@P:R=(B*R)@P:N=(C*N)@P
  18.   200   until N=1
  19.   210   return ' End of subroutine Ressol.
  20.